1151. Treasure Hunter
Young treasure hunter Roma has completed a
course in “treasure hunting” and has now set off for a summer internship. The
internship takes place near the village of “Stone Dawns” and lasts exactly b days. Each day, Roma
finds coins buried in the ground. Thus, by the end of the first day
he will have a coins, by the end of the second day – 2 * a, and
by the end of the internship Roma will have accumulated b * a coins.
If at the end of a day the supervising
instructor notices that the number of coins Roma has is divisible by b,
Roma may take a pie from the shelf and eat it immediately. Help Roma determine
how many pies he will eat during the entire internship.
Input. Two integers a and b (1 ≤ a, b ≤ 109).
Output. Print the number of pies that Roma will eat during the internship.
|
Sample input |
Sample
output |
|
2 1 |
1 |
GCD
The number of pies eaten
by Roma is equal to GCD(a, b).
The function gcd computes the greatest common divisor of the
numbers a and b.
int gcd(int a, int b)
{
return (!b) ? a : gcd(b, a % b);
}
Read the input data.
scanf("%d %d", &a, &b);
Compute and print the answer.
d = gcd(a, b);
printf("%d\n", d);